package LearnDataStructure.c_树结构.例题;
import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-13 18:45
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
给一个二叉树source
source很大，有上百万分支
给一个小树target
判断小树是否为大树的子树

用递归
 */
public class k_检查大树是否包含小树 {

    public static void main(String[] args) {
        k_检查大树是否包含小树 test = new k_检查大树是否包含小树();
        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree = new b_MyBinaryTreebyLinked<Integer,Integer>();
        binaryTree.insert(6,6);
        binaryTree.insert(7, 7);
        binaryTree.insert(4,4);
        BSTNode<Integer, Integer> q = binaryTree.insert(5, 5);
        binaryTree.insert(8, 8);
        BSTNode<Integer, Integer> p = binaryTree.insert(2, 2);

        b_MyBinaryTreebyLinked<Integer,Integer> smallTree = new b_MyBinaryTreebyLinked<Integer,Integer>();
        smallTree.insert(4,4);
        smallTree.insert(2,2);
        smallTree.insert(5,5);


        System.out.println(binaryTree);
        System.out.println(smallTree);
        boolean b = test.useCheck(binaryTree.getRoot(), smallTree.getRoot());
        System.out.println(b);
    }

    /**
     * 使用迭代，节省空间和时间
     * @param node
     * @param target
     * @return
     */
    public boolean useCheck(BSTNode<Integer, Integer> node, BSTNode<Integer, Integer> target) {
        Queue<BSTNode<Integer, Integer>> queue = new LinkedList<BSTNode<Integer, Integer>>();
        boolean flag = false;
        queue.add(node);
        do {
            BSTNode<Integer, Integer> poll = queue.poll();
            if (poll.key.equals(target.key)) {
                flag = check(poll,target);
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        } while (!flag && !queue.isEmpty());
        return flag;
    }

    public boolean check(BSTNode<Integer, Integer> node, BSTNode<Integer, Integer> target) {
        Queue<BSTNode<Integer, Integer>> queue = new LinkedList<BSTNode<Integer, Integer>>();
        if (node.left == null && target.left == null) {

        } else if (node.left != null && target.left != null) {
            queue.add(node.left);
            queue.add(target.left);
        } else {
            return false;
        }
        if (node.right == null && target.right == null) {

        } else if (node.right != null && target.right != null) {
            queue.add(node.right);
            queue.add(target.right);
        } else {
            return false;
        }

        boolean flag = true;

        do {
            BSTNode<Integer, Integer> fromNode = queue.poll();
            BSTNode<Integer, Integer> fromTarget = queue.poll();

            flag = fromNode.key.equals(fromTarget.key);

            if (fromNode.left == null && fromTarget.left == null) {

            } else if (fromNode.left != null && fromTarget.left != null) {
                queue.add(fromNode.left);
                queue.add(fromTarget.left);
            } else {
                return false;
            }
            if (fromNode.right == null && fromTarget.right == null) {

            } else if (fromNode.right != null && fromTarget.right != null) {
                queue.add(fromNode.right);
                queue.add(fromTarget.right);
            } else {
                return false;
            }

        } while (flag && !queue.isEmpty());

        if (flag) {
            return true;
        } else {
            return false;
        }
    }
}
